{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quick Find Algorithm to Merge Groups with Common Elements\n",
    "\n",
    "This is just a variation of the quick find algorithm.\n",
    "\n",
    "This algorithms combines two or more groups when they have common elements.\n",
    "\n",
    "The key is to use two temporary list. \n",
    "The first is called **elements**, which stores all elements existing in all groups.\n",
    "The second is named **labels**. Here I simply let the first element in the cluster be the centroid. Initially, the values are from 0 to length-1, ascendingly. \n",
    "\n",
    "For each group, I get their 'indices' in 'elements'.\n",
    "I then get the **labels for group** according to indices.\n",
    "And I calculate the min of the labels, that will be the new label for them.\n",
    "I replace all elements with labels in **labels for group** with the new label.\n",
    "    \n",
    "Or to say, for each iteration,\n",
    "I try to combine two or more existing groups.\n",
    "If the group has labels of 0 and 2\n",
    "I find out the new label 0, that is the min of the two.\n",
    "I than replace them with 0.\n",
    "\n",
    "## Example:\n",
    "\n",
    "We have the following list of strings, or list of lists of chars <br>\n",
    "**['ab','cd','bc','ef','fg','j','hi','ij']**\n",
    "\n",
    "the elements and inital labels are: <br>\n",
    "elements: <br>\n",
    "**['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']** <br>\n",
    "labels: <br>\n",
    "**[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]**\n",
    "\n",
    "For iteration 0: <br>\n",
    "--------------------group 0------------------------- <br>\n",
    "the group is: <br>\n",
    "ab <br>\n",
    "indices for the group in elements <br>\n",
    "[0, 1] <br>\n",
    "labels before combination <br>\n",
    "[0, **1**, 2, 3, 4, 5, 6, 7, 8, 9]  <br>\n",
    "combining... <br>\n",
    "labels after combination <br>\n",
    "[0, **0**, 2, 3, 4, 5, 6, 7, 8, 9] \n",
    "\n",
    "Here the elements of the group are **a** and **b**, there are the **first** and **second** items of the list **elements**.\n",
    "So, we find the **first** and **second** items in **labels**, they are **0** and **1**.\n",
    "This means we are going to combine **Group 0** and **Group 1**, and the new group is labelled **0** (min(0,1)=0).\n",
    "We go to **labels** and replace all **1s** with **0s**.\n",
    "\n",
    "For iteration 1: <br>\n",
    "--------------------group 1------------------------- <br>\n",
    "the group is: <br>\n",
    "cd <br>\n",
    "indices for the group in elements <br>\n",
    "[2, 3] <br>\n",
    "labels before combination <br>\n",
    "[0, 0, 2, **3**, 4, 5, 6, 7, 8, 9] <br>\n",
    "combining... <br>\n",
    "labels after combination <br>\n",
    "[0, 0, 2, **2**, 4, 5, 6, 7, 8, 9] \n",
    "\n",
    "Here the elements of the group are **c** and **d**, there are the **third** and **fourth** items of the list **elements**.\n",
    "So, we find the **third** and **fourth** items in **labels**, they are **2** and **3**.\n",
    "This means we are going to combine **Group 2** and **Group 3**, and the new group is labelled **2** (min(2,3)=2).\n",
    "We go to **labels** and replace all **3s** with **2s**.\n",
    "\n",
    "For iteration 2: <br>\n",
    "--------------------group 2------------------------- <br>\n",
    "the group is: <br>\n",
    "bc <br>\n",
    "indices for the group in elements <br>\n",
    "[1, 2] <br>\n",
    "labels before combination <br>\n",
    "[0, 0, **2**, **2**, 4, 5, 6, 7, 8, 9] <br>\n",
    "combining... <br>\n",
    "labels after combination <br>\n",
    "[0, 0, **0**, **0**, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "Here the elements of the group are **b** and **c**, there are the **second** and **third** items of the list **elements**.\n",
    "So, we find the **second** and **third** items in **labels**, they are **0** and **2**.\n",
    "This means we are going to combine **Group 0** and **Group 2**, and the new group is labelled **0** (min(0,2)=0).\n",
    "We go to **labels** and replace all **2s** with **0s**.\n",
    "\n",
    "...\n",
    "\n",
    "Finally, **labels** is:<br>\n",
    "[0, 0, 0, 0, 4, 4, 4, 7, 7, 7]<br>\n",
    "and the new groups are:<br>\n",
    "[['a', 'b', 'c', 'd'], ['e', 'f', 'g'], ['h', 'i', 'j']])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cluser_combine(groups):\n",
    "    n_groups=len(groups)\n",
    "    \n",
    "    #first, we put all elements appeared in 'gruops' into 'elements'.\n",
    "    elements=list(set.union(*[set(g) for g in groups]))\n",
    "    #and sort elements.\n",
    "    elements.sort()\n",
    "    print(\"elements:\")\n",
    "    print(elements)\n",
    "    n_elements=len(elements)\n",
    "    \n",
    "    labels=list(range(n_elements))\n",
    "    print(\"labels:\")\n",
    "    print(labels) \n",
    "    \n",
    "    #for each group, I get their 'indices' in 'elements'\n",
    "    #I then get the labels for indices.\n",
    "    #and i calculate the min of the labels, that will be the new label for them.\n",
    "    #I replace all elements with labels in labels_for_group with the new label.\n",
    "    \n",
    "    #or to say, for each iteration,\n",
    "    #i try to combine two or more existing groups.\n",
    "    #if the group has labels of 0 and 2\n",
    "    #i find out the new label 0, that is the min of the two.\n",
    "    #i than replace them with 0.\n",
    "    for i in range(n_groups):\n",
    "        print(f'--------------------group {i}-------------------------')\n",
    "\n",
    "        print('the group is:')\n",
    "        print(groups[i]) \n",
    "        #if there is only zero/one element in the group, skip\n",
    "        if len(groups[i])<=1:\n",
    "            continue\n",
    "            \n",
    "        indices=list(map(elements.index, groups[i]))\n",
    "        print('indices for the group in elements') \n",
    "        print(indices) \n",
    "        labels_for_group=list(set([labels[i] for i in indices]))\n",
    "        #if their is only one label, all the elements in group are already have the same label, skip.\n",
    "        if len(labels_for_group)==1:\n",
    "            print('their is only one label, skip')\n",
    "            continue\n",
    "            \n",
    "        labels_for_group.sort()\n",
    "        label=labels_for_group[0]\n",
    "        print('labels before combination')\n",
    "        print(labels) \n",
    "        print('combining...')\n",
    "        #combine\n",
    "        for k in range(n_elements):\n",
    "            if labels[k] in labels_for_group[1:]:\n",
    "                labels[k]=label\n",
    "        \n",
    "        print('labels after combination')\n",
    "        print(labels) \n",
    "    \n",
    "    new_groups=[]\n",
    "    for label in set(labels):\n",
    "        new_group = [elements[i] for i, v in enumerate(labels) if v == label]\n",
    "        new_groups.append(new_group)\n",
    "\n",
    "    return labels, new_groups\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elements:\n",
      "['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']\n",
      "labels:\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 0-------------------------\n",
      "the group is:\n",
      "ab\n",
      "indices for the group in elements\n",
      "[0, 1]\n",
      "labels before combination\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 1-------------------------\n",
      "the group is:\n",
      "cd\n",
      "indices for the group in elements\n",
      "[2, 3]\n",
      "labels before combination\n",
      "[0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 2, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 2-------------------------\n",
      "the group is:\n",
      "bc\n",
      "indices for the group in elements\n",
      "[1, 2]\n",
      "labels before combination\n",
      "[0, 0, 2, 2, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 0, 0, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 3-------------------------\n",
      "the group is:\n",
      "ef\n",
      "indices for the group in elements\n",
      "[4, 5]\n",
      "labels before combination\n",
      "[0, 0, 0, 0, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 0, 0, 4, 4, 6, 7, 8, 9]\n",
      "--------------------group 4-------------------------\n",
      "the group is:\n",
      "fg\n",
      "indices for the group in elements\n",
      "[5, 6]\n",
      "labels before combination\n",
      "[0, 0, 0, 0, 4, 4, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 0, 0, 4, 4, 4, 7, 8, 9]\n",
      "--------------------group 5-------------------------\n",
      "the group is:\n",
      "j\n",
      "--------------------group 6-------------------------\n",
      "the group is:\n",
      "hi\n",
      "indices for the group in elements\n",
      "[7, 8]\n",
      "labels before combination\n",
      "[0, 0, 0, 0, 4, 4, 4, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 0, 0, 4, 4, 4, 7, 7, 9]\n",
      "--------------------group 7-------------------------\n",
      "the group is:\n",
      "ij\n",
      "indices for the group in elements\n",
      "[8, 9]\n",
      "labels before combination\n",
      "[0, 0, 0, 0, 4, 4, 4, 7, 7, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 0, 0, 4, 4, 4, 7, 7, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([0, 0, 0, 0, 4, 4, 4, 7, 7, 7],\n",
       " [['a', 'b', 'c', 'd'], ['e', 'f', 'g'], ['h', 'i', 'j']])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluser_combine(['ab','cd','bc','ef','fg','j','hi','ij'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elements:\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "labels:\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 0-------------------------\n",
      "the group is:\n",
      "[7, 8]\n",
      "indices for the group in elements\n",
      "[7, 8]\n",
      "labels before combination\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 7, 9]\n",
      "--------------------group 1-------------------------\n",
      "the group is:\n",
      "[1, 2]\n",
      "indices for the group in elements\n",
      "[1, 2]\n",
      "labels before combination\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 7, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 1, 1, 3, 4, 5, 6, 7, 7, 9]\n",
      "--------------------group 2-------------------------\n",
      "the group is:\n",
      "[2, 3]\n",
      "indices for the group in elements\n",
      "[2, 3]\n",
      "labels before combination\n",
      "[0, 1, 1, 3, 4, 5, 6, 7, 7, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 1, 1, 1, 4, 5, 6, 7, 7, 9]\n",
      "--------------------group 3-------------------------\n",
      "the group is:\n",
      "[3, 4]\n",
      "indices for the group in elements\n",
      "[3, 4]\n",
      "labels before combination\n",
      "[0, 1, 1, 1, 4, 5, 6, 7, 7, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 1, 1, 1, 1, 5, 6, 7, 7, 9]\n",
      "--------------------group 4-------------------------\n",
      "the group is:\n",
      "[5, 6]\n",
      "indices for the group in elements\n",
      "[5, 6]\n",
      "labels before combination\n",
      "[0, 1, 1, 1, 1, 5, 6, 7, 7, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 1, 1, 1, 1, 5, 5, 7, 7, 9]\n",
      "--------------------group 5-------------------------\n",
      "the group is:\n",
      "[8, 9]\n",
      "indices for the group in elements\n",
      "[8, 9]\n",
      "labels before combination\n",
      "[0, 1, 1, 1, 1, 5, 5, 7, 7, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 1, 1, 1, 1, 5, 5, 7, 7, 7]\n",
      "--------------------group 6-------------------------\n",
      "the group is:\n",
      "[0]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([0, 1, 1, 1, 1, 5, 5, 7, 7, 7], [[0], [1, 2, 3, 4], [5, 6], [7, 8, 9]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluser_combine([[7,8],[1,2],[2,3],[3,4],[5,6],[8,9],[0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "elements:\n",
      "['a', 'b', 'c', 'd', 'e', 'l', 'o', 'p', 's', 't']\n",
      "labels:\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 0-------------------------\n",
      "the group is:\n",
      "ab\n",
      "indices for the group in elements\n",
      "[0, 1]\n",
      "labels before combination\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 1-------------------------\n",
      "the group is:\n",
      "cd\n",
      "indices for the group in elements\n",
      "[2, 3]\n",
      "labels before combination\n",
      "[0, 0, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 2, 4, 5, 6, 7, 8, 9]\n",
      "--------------------group 2-------------------------\n",
      "the group is:\n",
      "aeo\n",
      "indices for the group in elements\n",
      "[0, 4, 6]\n",
      "labels before combination\n",
      "[0, 0, 2, 2, 4, 5, 6, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 2, 0, 5, 0, 7, 8, 9]\n",
      "--------------------group 3-------------------------\n",
      "the group is:\n",
      "lp\n",
      "indices for the group in elements\n",
      "[5, 7]\n",
      "labels before combination\n",
      "[0, 0, 2, 2, 0, 5, 0, 7, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 2, 0, 5, 0, 5, 8, 9]\n",
      "--------------------group 4-------------------------\n",
      "the group is:\n",
      "ts\n",
      "indices for the group in elements\n",
      "[9, 8]\n",
      "labels before combination\n",
      "[0, 0, 2, 2, 0, 5, 0, 5, 8, 9]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 2, 0, 5, 0, 5, 8, 8]\n",
      "--------------------group 5-------------------------\n",
      "the group is:\n",
      "op\n",
      "indices for the group in elements\n",
      "[6, 7]\n",
      "labels before combination\n",
      "[0, 0, 2, 2, 0, 5, 0, 5, 8, 8]\n",
      "combining...\n",
      "labels after combination\n",
      "[0, 0, 2, 2, 0, 0, 0, 0, 8, 8]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([0, 0, 2, 2, 0, 0, 0, 0, 8, 8],\n",
       " [['a', 'b', 'e', 'l', 'o', 'p'], ['s', 't'], ['c', 'd']])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cluser_combine(['ab','cd','aeo','lp','ts','op'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A clean version:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cluser_combine(groups):\n",
    "    n_groups=len(groups)\n",
    "    \n",
    "    #first, we put all elements appeared in 'gruops' into 'elements'.\n",
    "    elements=list(set.union(*[set(g) for g in groups]))\n",
    "    #and sort elements.\n",
    "    elements.sort()\n",
    "    n_elements=len(elements)\n",
    "    \n",
    "    labels=list(range(n_elements))\n",
    "\n",
    "    \n",
    "    #for each group, I get their 'indices' in 'elements'\n",
    "    #I then get the labels for indices.\n",
    "    #and i calculate the min of the labels, that will be the new label for them.\n",
    "    #I replace all elements with labels in labels_for_group with the new label.\n",
    "    \n",
    "    #or to say, for each iteration,\n",
    "    #i try to combine two or more existing groups.\n",
    "    #if the group has labels of 0 and 2\n",
    "    #i find out the new label 0, that is the min of the two.\n",
    "    #i than replace them with 0.\n",
    "    for i in range(n_groups):\n",
    "\n",
    "        #if there is only zero/one element in the group, skip\n",
    "        if len(groups[i])<=1:\n",
    "            continue\n",
    "            \n",
    "        indices=list(map(elements.index, groups[i]))\n",
    "\n",
    "        labels_for_group=list(set([labels[i] for i in indices]))\n",
    "        #if their is only one label, all the elements in group are already have the same label, skip.\n",
    "        if len(labels_for_group)==1:\n",
    "\n",
    "            continue\n",
    "            \n",
    "        labels_for_group.sort()\n",
    "        label=labels_for_group[0]\n",
    "\n",
    "        #combine\n",
    "        for k in range(n_elements):\n",
    "            if labels[k] in labels_for_group[1:]:\n",
    "                labels[k]=label\n",
    "\n",
    "    \n",
    "    new_groups=[]\n",
    "    for label in set(labels):\n",
    "        new_group = [elements[i] for i, v in enumerate(labels) if v == label]\n",
    "        new_groups.append(new_group)\n",
    "\n",
    "    return labels, new_groups"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
